package exercise.基础练习;

import java.util.ArrayList;
import java.util.HashMap;

public class LC076_最小覆盖子串 {
    public static void main(String[] args) {

    }

    public String minWindow(String s, String t) {
        HashMap<Character,Integer> currentMap = new HashMap<>();//当前
        HashMap<Character,Integer> needMap = new HashMap<>();//需求
        for(int i = 0;i < t.length();i++){
            needMap.put(t.charAt(i),needMap.getOrDefault(t.charAt(i),0) + 1);
        }
        int left = 0,right = 0,valid = 0;//左窗口、右窗口、已匹配的字符个数
        int start = 0,res_length = Integer.MAX_VALUE;//答案的起点下标，持续长度
        while(right < s.length()){
            //右侧窗口向后移动，c是移入窗口的字符
            char c = s.charAt(right++);
            //当新移入的字符在需求中存在，存入当前哈希
            if(needMap.get(c) != null){
                currentMap.put(c,currentMap.getOrDefault(c,0) + 1);
                //当前字符出现次数等于需求时，匹配字符数+1
                if(currentMap.get(c).equals(needMap.get(c))){
                    valid++;//已匹配的字符个数+1
                }
            }
            //当已匹配的字符数满足需求时，左侧窗口向后移动
            while(valid == needMap.size()){
                //当右窗口-左窗口小于结果长度时，更新结果
                if(right - left < res_length){
                    start = left;
                    res_length = right - left;
                }
                //左侧窗口向后移动，c是移出窗口的字符
                c = s.charAt(left++);
                //移出的字符在需求中存在
                if(needMap.get(c) != null){
                    //移出的字符出现次数与需求相等，则移出后就不相等了
                    if(currentMap.get(c).equals(needMap.get(c))){
                        valid--;//此行一旦执行，说明窗口内字符串已经不满足需求，左侧窗口停止移动
                    }
                    currentMap.put(c,currentMap.get(c) - 1);
                }
            }
        }
        if(res_length != Integer.MAX_VALUE){
            return s.substring(start,start + res_length);
        } else {
            return "";
        }
    }
}
